home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / checkedc.jav < prev    next >
Text File  |  1995-12-14  |  16KB  |  551 lines
  1. /*
  2.   File: CheckedCollection.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Misc clean-up.
  12.   19Oct95  dl                 more misc clean-up.
  13.  
  14. */
  15.   
  16. package collections;
  17.  
  18. import java.util.Enumeration;
  19. import java.util.NoSuchElementException;
  20.  
  21. /**
  22.  *
  23.  * Base class for  Collection testing.
  24.  * CheckCollections are simple harnesses around other Collections.
  25.  * They include constructors that accept any other kind of collection, c.
  26.  * They mirror each operation in the corresponding interface.
  27.  * For each operation, they invoke c.checkImplementation(),
  28.  * then operate upon c,
  29.  * then check for as many testable effects of the operation
  30.  * as is feasible, and then recheck c. 
  31.  * <P>
  32.  * This is not usually very fast. Among other reasons,
  33.  * checks often require that copies of state be made to compare against later.
  34.  * <P>
  35.  * @author Doug Lea
  36.  * @version 0.94
  37.  *
  38.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  39. **/
  40.  
  41. public class CheckedCollection implements UpdatableCollection  {
  42.  
  43. /**
  44.  * The collection performing the actual work.
  45.  * (All instance variables are public so can be inspected easily in tests)
  46. **/
  47.  
  48.   public UpdatableCollection thys;
  49.   
  50. /**
  51.  * A clone of the thys made before an operation
  52. **/
  53.  
  54.   public UpdatableCollection prev;
  55.  
  56.  
  57. /**
  58.  * The version number of thys before an operation
  59. **/
  60.  
  61.   public int prevVersion;
  62.  
  63. /**
  64.  * Wrap collection c in inside a Checker
  65. **/
  66.  
  67.   public CheckedCollection(UpdatableCollection c) { 
  68.     thys = c; 
  69.     thys.checkImplementation();
  70.   }
  71.  
  72. /**
  73.  * Make a Checked clone of underlying collection
  74. **/
  75.   protected Object clone() throws CloneNotSupportedException { 
  76.     return new CheckedCollection((UpdatableCollection)(thys.duplicate()));
  77.   }
  78.  
  79.  
  80. /**
  81.  * Wrapper for clone()
  82.  * @see clone
  83. **/
  84.  
  85.  public synchronized Collection duplicate() { 
  86.    Collection c = null;
  87.    try {
  88.      c = (Collection)(this.clone()); 
  89.     } catch (CloneNotSupportedException ex) {}
  90.    return c;
  91.  }
  92.  
  93.  
  94. /**
  95.  * Call at the end of any checked method
  96. **/
  97.  
  98.   protected void postCheck() {
  99.     thys.checkImplementation();
  100.     prev = null; // side effect -- detach prev so GC can claim it
  101.   }
  102.  
  103. /**
  104.  * Call at the beginnning of any checked method requiring
  105.  * use of prev clone
  106. **/
  107.  
  108.   protected void preCheck() {
  109.     prev = (UpdatableCollection)(thys.duplicate());
  110.     prevVersion = thys.version();
  111.   }
  112.   
  113. /**
  114.  * Checks collections.Collection.canInclude according to its specification
  115.  * @see collections.Collection#canInclude
  116. **/
  117.   public synchronized boolean     canInclude(Object element) {
  118.     preCheck(); 
  119.     boolean result = thys.canInclude(element);
  120.     // not allowed to report true for null
  121.     assert(!(result == true && element == null));
  122.     // must be side-effect free
  123.     assert(thys.sameStructure(prev));
  124.     postCheck();
  125.     return result;
  126.   }
  127.  
  128. /**
  129.  * Checks collections.Collection.isEmpty according to its specification
  130.  * @see collections.Collection#isEmpty
  131. **/
  132.   public synchronized boolean     isEmpty() {
  133.     preCheck(); 
  134.     boolean result = thys.isEmpty();
  135.     // must be behaviorally equivalent to asking if size() == 0
  136.     assert(result == (thys.size() == 0));
  137.     assert(thys.sameStructure(prev));
  138.     postCheck();
  139.     return result;
  140.   }
  141.  
  142. /**
  143.  * Checks collections.Collection.size according to its specification
  144.  * @see collections.Collection#size
  145. **/
  146.   public synchronized  int         size() {
  147.     preCheck(); 
  148.     int result = thys.size();
  149.     // sizes are non-negative
  150.     assert(result >= 0);
  151.     // cross-check of isEmpty assertion
  152.     assert( (result == 0) == thys.isEmpty());
  153.     assert(thys.sameStructure(prev));
  154.     postCheck();
  155.     return result;
  156.   }
  157.  
  158.  
  159.  
  160. /**
  161.  * Checks collections.Collection.occurrencesOf according to its specification
  162.  * @see collections.Collection#occurrencesOf
  163. **/
  164.   public synchronized int         occurrencesOf(Object element) {
  165.     preCheck(); 
  166.     int result = thys.occurrencesOf(element);
  167.     // occurrences are non-negative
  168.     assert((result >= 0));
  169.     // cannot be greater than size()
  170.     assert(result <= thys.size());
  171.     // occurrences of things you canot include must be 0
  172.     assert(thys.canInclude(element) || result == 0);
  173.     // cross-check of include condition
  174.     assert( !((result == 0) && thys.includes(element)));
  175.     assert(thys.sameStructure(prev));
  176.     postCheck();
  177.     return result;
  178.   }
  179.  
  180. /**
  181.  * Checks collections.Collection.includes according to its specification
  182.  * @see collections.Collection#includes
  183. **/
  184.   public synchronized boolean     includes(Object element) {
  185.     preCheck(); 
  186.     boolean result = thys.includes(element);
  187.     // must be equiv to asking if occurrences >= 1
  188.     assert(result == (thys.occurrencesOf(element) >= 1));
  189.     assert(thys.sameStructure(prev));
  190.     postCheck();
  191.     return result;
  192.   }
  193.  
  194. /**
  195.  * Checks collections.Collection.elements according to its specification
  196.  * @see collections.Collection#elements
  197. **/
  198.   public synchronized CollectionEnumeration elements() {
  199.     // get one and make sure it is OK
  200.     int c = thys.size();
  201.     CollectionEnumeration e = thys.elements();
  202.     while (e.hasMoreElements()) {
  203.       // reports correct number of elements
  204.       assert(e.numberOfRemainingElements() == c);
  205.       --c;
  206.       Object v = e.nextElement();
  207.       // each element reported actually occurs
  208.       assert(thys.includes(v));
  209.     }
  210.     // We've exhausted e; return another one
  211.     postCheck(); 
  212.     return thys.elements();
  213.   }
  214.  
  215.  
  216. /**
  217.  * Checks collections.Collection.sameStructure according to its specification
  218.  * @see collections.Collection#sameStructure
  219. **/
  220.   public synchronized boolean sameStructure(Collection c) {
  221.     // cannot check since we rely on it to check other assertions
  222.     boolean result = thys.sameStructure(c);
  223.     postCheck();
  224.     return result;
  225.   }
  226.  
  227. /** 
  228.  * Implements Object.toString
  229. **/
  230.   public String toString() {
  231.     // cannot check
  232.     String result = thys.toString();
  233.     postCheck();
  234.     return result;
  235.   }
  236.  
  237. /** 
  238.  * Checks collections.UpdatableCollection.version according to its specification
  239.  * @see collections.UpdatableCollection#version
  240. **/
  241.   public synchronized int         version() {
  242.     // nothing to check
  243.     int result = thys.version();
  244.     postCheck();
  245.     return result;
  246.   }
  247.  
  248. /**
  249.  * Checks collections.UpdatableCollection.clear according to its specification
  250.  * @see collections.UpdatableCollection#clear
  251. **/
  252.   public synchronized void        clear() {
  253.     preCheck();
  254.     thys.clear();
  255.     // mst now be empty
  256.     assert(thys.isEmpty());
  257.     // version change only if not previously empty
  258.     assert((thys.version() == prevVersion) == prev.isEmpty());
  259.     postCheck();
  260.   }
  261.  
  262.  
  263. /**
  264.  * Checks collections.UpdatableCollection.exclude according to its specification
  265.  * @see collections.UpdatableCollection#exclude
  266. **/
  267.   public synchronized void exclude(Object element) {
  268.     preCheck();
  269.     thys.exclude(element);
  270.     checkRemove(thys, prev, element, true, true);
  271.     postCheck();
  272.   }
  273.  
  274.  
  275. /**
  276.  * Checks collections.Collection.excluding.
  277.  * @see collections.Collection#excluding
  278. **/
  279.   public synchronized Collection excluding(Object element) {
  280.     preCheck();
  281.     Collection nc = thys.excluding(element);
  282.     checkRemove(nc, thys, element, true, false);
  283.     assert(thys.sameStructure(prev));
  284.     postCheck();
  285.     return nc;
  286.   }
  287.  
  288.  
  289. /**
  290.  * Checks collections.UpdatableCollection.removeOneOf according to its specification
  291.  * @see collections.UpdatableCollection#removeOneOf
  292. **/
  293.   public synchronized void removeOneOf(Object element) {
  294.     preCheck();
  295.     thys.removeOneOf(element);
  296.     checkRemove(thys, prev, element, false, true);
  297.     postCheck();
  298.   }
  299.  
  300. /**
  301.  * Checks collections.Collection.removingOneOf
  302.  * @see collections.Collection#removingOneOf
  303. **/
  304.   public synchronized Collection removingOneOf(Object element) {
  305.     preCheck();
  306.     Collection nc = thys.removingOneOf(element);
  307.     checkRemove(nc, thys, element, false, false);
  308.     assert(thys.sameStructure(prev));
  309.     postCheck();
  310.     return nc;
  311.   }
  312.  
  313.  
  314.  
  315. /**
  316.  * Checks collections.UpdatableCollection.replaceOneOf according to its specification
  317.  * @see collections.UpdatableCollection#replaceOneOf
  318. **/
  319.   public synchronized void replaceOneOf(Object oldElement, Object newElement) 
  320.   throws IllegalElementException {
  321.     preCheck();
  322.     try {
  323.       thys.replaceOneOf(oldElement, newElement);
  324.       checkReplace(thys, prev, oldElement, newElement, false, true);
  325.       postCheck();
  326.     }
  327.     catch(IllegalElementException ex) {
  328.       assert(thys.includes(oldElement) && !thys.canInclude(newElement));
  329.       assert(thys.sameStructure(prev));
  330.       postCheck();
  331.       throw ex;
  332.     }
  333.   }
  334.  
  335. /**
  336.  * Checks collections.Collection.replacingOneOf
  337.  * @see collections.Collection#replacingOneOf
  338. **/
  339.   public synchronized Collection replacingOneOf(Object oldElement,
  340.                                                 Object newElement) 
  341.   throws IllegalElementException {
  342.     preCheck();
  343.     try {
  344.       Collection nc = thys.replacingOneOf(oldElement, newElement);
  345.       checkReplace(nc, thys, oldElement, newElement, false, false);
  346.       assert(thys.sameStructure(prev));
  347.       postCheck();
  348.       return nc;
  349.     }
  350.     catch(IllegalElementException ex) {
  351.       assert(thys.includes(oldElement) && !thys.canInclude(newElement));
  352.       assert(thys.sameStructure(prev));
  353.       postCheck();
  354.       throw ex;
  355.     }
  356.  
  357.   }
  358.  
  359. /**
  360.  * Checks collections.UpdatableCollection.replaceAllOf according to its specification
  361.  * @see collections.UpdatableCollection#replaceAllOf
  362. **/
  363.   public synchronized void replaceAllOf(Object oldElement, Object newElement) 
  364.   throws IllegalElementException {
  365.     preCheck();
  366.     try {
  367.       thys.replaceAllOf(oldElement, newElement);
  368.       checkReplace(thys, prev, oldElement, newElement, true, true);
  369.       postCheck();
  370.     }
  371.     catch(IllegalElementException ex) {
  372.       assert(thys.includes(oldElement) && !thys.canInclude(newElement));
  373.       assert(thys.sameStructure(prev));
  374.       postCheck();
  375.       throw ex;
  376.     }
  377.   }
  378.  
  379. /**
  380.  * Checks collections.Collection.replacingAllOf
  381.  * @see collections.Collection#replacingAllOf
  382. **/
  383.   public synchronized Collection replacingAllOf(Object oldElement,
  384.                                                 Object newElement) 
  385.   throws IllegalElementException {
  386.     preCheck();
  387.     try {
  388.       Collection nc = thys.replacingAllOf(oldElement, newElement);
  389.       checkReplace(nc, thys, oldElement, newElement, true, false);
  390.       assert(thys.sameStructure(prev));
  391.       postCheck();
  392.       return nc;
  393.     }
  394.     catch(IllegalElementException ex) {
  395.       assert(thys.includes(oldElement) && !thys.canInclude(newElement));
  396.       assert(thys.sameStructure(prev));
  397.       postCheck();
  398.       throw ex;
  399.     }
  400.  
  401.   }
  402.  
  403. /**
  404.  * Checks collections.UpdatableCollection.take according to its specification
  405.  * @see collections.UpdatableCollection#take
  406. **/
  407.   public Object take() throws NoSuchElementException {
  408.     preCheck();
  409.     try {
  410.       Object result = thys.take();
  411.       assert(result != null);
  412.       checkRemove(thys, prev, result, false, true);
  413.       postCheck();
  414.       return result;
  415.     }
  416.     catch (NoSuchElementException ex) {
  417.       assert(prev.isEmpty());
  418.       assert(thys.sameStructure(prev));
  419.       postCheck();
  420.       throw ex;
  421.     }
  422.   }
  423.  
  424.  
  425. /** 
  426.  * Checks collections.UpdatableCollection.excludeElements
  427.  * @see collections.UpdatableCollection#excludeElements
  428. **/
  429.   public synchronized void excludeElements(Enumeration e) 
  430.   throws CorruptedEnumerationException {
  431.     preCheck();
  432.     thys.excludeElements(e);
  433.     // can't check elements since e has been exhausted --
  434.     // we have no handle to them.
  435.     postCheck();
  436.   }
  437.  
  438.  
  439. /** 
  440.  * Checks collections.UpdatableCollection.removeElements
  441.  * @see collections.UpdatableCollection#removeElements
  442. **/
  443.   public synchronized void removeElements(Enumeration e) 
  444.   throws CorruptedEnumerationException {
  445.     preCheck();
  446.     thys.removeElements(e);
  447.     // Same problem as above
  448.     postCheck();
  449.   }
  450.  
  451. /**
  452.  * Implements collections.ImplementationCheckable.assert.
  453.  * @see collections.ImplementationCheckable#assert
  454. **/
  455.   public void assert(boolean pred) 
  456.   throws ImplementationError {
  457.     ImplementationError.assert(thys, pred);
  458.   }
  459.  
  460.  
  461. /**
  462.  * Implements collections.ImplementationCheckable.checkImplementation
  463.  * @see collections.ImplementationCheckable#checkImplementation
  464. **/
  465.   public synchronized void checkImplementation()
  466.   throws ImplementationError {
  467.     // we cannot check ourselves!
  468.   }
  469.  
  470. /**
  471.  * Helper for checking remov*, exclud*, take
  472. **/
  473.  
  474.   protected void checkRemove(Collection nc, Collection oc,
  475.                  Object element,
  476.                  boolean allOccurrences, boolean verchk) {
  477.     int prevOcc = oc.occurrencesOf(element);
  478.     int reqOcc = 0;
  479.     if (!allOccurrences && prevOcc > 1)
  480.       reqOcc =  prevOcc - 1;
  481.     int newOcc = nc.occurrencesOf(element);
  482.  
  483.     assert(newOcc == reqOcc);
  484.  
  485.     // size reflects removals
  486.     assert(nc.size() == oc.size() - (prevOcc - newOcc));
  487.  
  488.     if (verchk) {
  489.       // version change only if occurrences change
  490.       int nv = ((UpdatableCollection)nc).version();
  491.       assert((nv == prevVersion) == (prevOcc == newOcc));
  492.     }
  493.  
  494.     // all other elements the same
  495.     CollectionEnumeration os = oc.elements();
  496.     while (os.hasMoreElements()) {
  497.       Object v = os.nextElement();
  498.       assert(!v.equals(element) == 
  499.              (nc.occurrencesOf(v) == oc.occurrencesOf(v)));
  500.     }
  501.  
  502.     nc.checkImplementation();
  503.  
  504.   }
  505.  
  506. /**
  507.  * Helper for checking replac*
  508. **/
  509.   protected void checkReplace(Collection nc, Collection oc,
  510.                   Object oldElement, Object newElement,
  511.                   boolean allOccurrences, boolean verchk) {
  512.     int delta = prev.occurrencesOf(oldElement);
  513.     // for OneOf, occurrences of old element == max(0, old occurrences - 1)
  514.     if (!allOccurrences && delta > 1) delta = 1;
  515.     // ... unless they are equal, in which case unchanged
  516.     if (oldElement.equals(newElement)) delta = 0;
  517.  
  518.     assert(nc.occurrencesOf(oldElement) == 
  519.        oc.occurrencesOf(oldElement) - delta);
  520.  
  521.     if (delta != 0)
  522.       assert(nc.canInclude(newElement));
  523.  
  524.     // new occurrences added by one 
  525.     int reqNewOcc = prev.occurrencesOf(newElement) + delta;
  526.     // .. unless it obeys Set semantics, in which case max of 1
  527.     if (reqNewOcc > 1 && (nc instanceof Set)) reqNewOcc = 1;
  528.  
  529.     assert(nc.occurrencesOf(newElement) == reqNewOcc);
  530.  
  531.     if (verchk) {
  532.       // version change only if occurrences change
  533.       int nv = ((UpdatableCollection)nc).version();
  534.       assert(!((nv == prevVersion) && (delta != 0)));;
  535.     }
  536.  
  537.     // all other elements the same
  538.  
  539.     CollectionEnumeration os = oc.elements();
  540.     while (os.hasMoreElements()) {
  541.       Object v = os.nextElement();
  542.       if (!v.equals(oldElement) && !v.equals(newElement))
  543.     assert(nc.occurrencesOf(v) == oc.occurrencesOf(v));
  544.     }
  545.  
  546.     nc.checkImplementation();
  547.   }
  548.  
  549. }
  550.  
  551.